package cn.xuchunh;

import java.util.Arrays;
import java.util.Random;

/**
 * Created by XuChunH on 2016/3/17.
 */
public class Main {

    public static void main(String[] args) {

        String[] result = train(new int[]{1, 2, 3, 4});
        for (String s : result) {
            System.out.println(s);
        }
    }

    /**
     * 标号0-(n-1)的n个人首尾相接，1到m(m > 1)报数，报到m的退出，求最后一个人的标号
     * f(n,m) = [f(n-1, m) + m] % n (n > 1), 当n=1时， 为0
     *
     * @return 最后剩余的那个编号
     */
    public static int numberOff(int n, int m) {
        if (n < 1 || m < 1) {
            return -1;
        }
        int last = 0;
        for (int i = 2; i <= n; i++) {
            last = (last + m) % i;
        }
        return last;
    }

    /**
     * 请把纸条竖着放在桌子上，然后从纸条的下边向上方对折，压出折痕后再展 开。此时有1条折痕，突起
     * 的方向指向纸条的背面这条折痕叫做“下”折痕 ；突起的⽅向指向纸条正面的折痕叫做“上”折痕。
     * 如果每次都从下边向上方对折，对折N次。请从上到下计算出所有折痕的方向。
     * 给定折的次数n,请返回从上到下的折痕的数组，若为下折痕则对应元素为"down",若为上折痕则为"up".
     *
     * @param n 折纸的次数
     * @return 从上往下的折痕方向
     */
    public static String[] foldPaper(int n) {
        // write code here
        if (n < 1) {
            return null;
        }
        if (n == 1) {
            return new String[]{"down"};
        }
        int length = (int) (Math.pow(2, n) - 1);
        String[] result = new String[length];
        String[] temp = foldPaper(n - 1);
        int i;
        for (i = 0; i < temp.length; i++) {
            result[i] = temp[i];
        }
        result[i] = "down";
        int j = i + 1;
        for (i = temp.length - 1; i >= 0; i--, j++) {
            result[j] = "down".equals(temp[i]) ? "up" : "down";
        }
        return result;
    }

    public static int[] random100() {
        int[] source = new int[100];
        int time = new Random().nextInt(50) + 25;
        for (int i = 0; i < 100; i++) {
            source[i] = i;
        }
        Random random = new Random();
        for (int i = 0; i < time; i++) {
            int a = random.nextInt(100);
            int b = random.nextInt(100);
            if (a == b) {
                i--;
                continue;
            } else {
                int temp = source[a];
                source[a] = source[b];
                source[b] = temp;
            }
        }
        return source;
    }

    /**
     * @param n1
     * @param n2
     * @param n3
     * @return 1 成功 0 失败
     */
    public static int letou(int[] source, int n1, int n2, int n3) {
        int max = source[0];
        int i;
        for (i = 0; i <= n1; i++) {
            if (max < source[i]) {
                max = source[i];
            }
        }
        for (; i < 100; i++) {
            if (source[i] > max) {
                if (source[i] == source.length - 1) {
                    return 1;
                }
                break;
            }
        }
        if (i > n2) {

        } else {

        }
        return 0;
    }

    /**
     * 火车进站
     *
     * @return 可能的出站顺序
     */
    public static String[] train(int[] source) {
        if (source.length > 0) {
            if (source.length == 1) {
                return new String[]{String.valueOf(source[0])};
            } else {
                String[] subResult = train(Arrays.copyOfRange(source, 1, source.length));
                String[] result = new String[subResult.length * 2];
                int i = 0;
                for (; i < subResult.length; i++) {
                    result[i] = source[0] + subResult[i];
                }
                for (; i < result.length; i++) {
                    result[i] = subResult[i - subResult.length] + source[0];
                }
                return result;
            }
        }

        return null;
    }


}
